#include <iostream>

void InsertSort(int *a,int n)
{
    for(int i=1;i<n;i++)
    {
        //找到第一个比他大的元素的位置或者走到头
        int end=i-1;
        int temp=a[end+1];
        while(end>=0)
        {
            if(a[end]>temp)
            {
                a[end+1]=a[end];
                end--;
            }
            else{
                break;
            }
        }
        //走到这就是要找的位置
        a[end+1]=temp;
    }
}

int main()
{
    int a[10]={5,3,6,9,7,1,0,2,4,10};
    InsertSort(a,10);
    for(int i=0;i<10;i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    return 0;
}